package org.taoge;


/**
 * 快读排序
 */
public class QuickSort {

    public static void main(String[] args) {
        int[] arr = {20, 1, 2, 40, 5, 7, 80};
        quickSort(arr, 0, arr.length - 1);
    }



    /**
     * 因为快速排序有递归的思想在，所以我们的方法签名，需要包含left和right为递归调用打下基础
     * 如果在方法内定义left和right就成了固定值，没法递归调用
     * 首次调用，high是数组长度-1
     */

    public static void quickSort(int[] arr, int low, int high){
        if(low < high){
            int pivotIndex = partition(arr, low, high);
            quickSort(arr, low, pivotIndex-1);
            quickSort(arr, pivotIndex+1, high);
        }
    }

    public static int partition(int[] arr, int low, int high){
        int pivot = arr[low]; //第一位作为首次基准值，然后用pivot存储第一位，后续遍历优先从右到左开始，以便于找到比基准小时，可以覆盖arr[low]，因为原有arr[low]已经存储起来
        while (low < high){
            //从右到左开始遍历，遇到大于基准值，则满足条件，继续向左
            while (low<high && arr[high] >= pivot){
                high--;
            }
            arr[low] = arr[high];
            //遇到小于基准值的，则将该值存放到i的位置，原有arr[i]已经存储，此时相当于arr[j]的值存在了两份，一份在j，一份在i
            // 20，1，2，40，5，7，80,执行第一次遍历，先比较80，j变成5，然后比较7，将7存放到arr[i]。顺序为：7，1，2，40，5，7，80

            //从左到右开始遍历，遇到小于基准值，则满足条件，继续向右
            while (low<high && arr[low] <= pivot){
                low++;
            }
            arr[high] = arr[low];
            //遇到大于基准值的，则将该值存放到arr[j]，上面的步骤执行后，原有arr[j]存放两份，所以我们把这次大于基准值的，放到右边的arr[j]处
            //基于7，1，2，40，5，7，80，先比较1,2满足，遇到40是的时候，将40放到右边7的位置.顺序为：7，1，2，40，5，40,80

            //经历上述后，我们的i是3，j是5.依然满足i<j,所以继续从右开始找
            //从右到左继续时，遇到5，将5继续放到40的位置：7，1，2，5，5，40,80  j=4
            //从左到右继续时，i=4时，依然满足，所以i=j，退出while

        }
        //将原有基准pivot，存放到arr[j]或者arr[i] ，i=j
        arr[low] = pivot;  //7，1，2，5，20，40,80,此时，20的左侧都比它小，右边都比他大。20的位置就相当于固定了，下面继续递归分别排序左右侧
        //7，1，2，5  和  40,80
        //0-3 和  5-6  0到j-1  和 j+1到high
        for (int value : arr) {
            System.out.print(value + " ");
        }
        System.out.println("返回的基准坐标："+low);
        return low;
    }
}
